package com.xiang.xian.tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Author Xian.Xiang
 * @Date 2024/6/18 16:59
 * @Version 1.0
 */
public class Solution {
    public static int res = 0;  // 1   2  //
    public static int maxDepth = 0;

    public static int maxDepth(TreeNode root) {
        setMaxDepth(root);
        return res;
    }

    // 最大深度
    public static void setMaxDepth(TreeNode root) {
        if (root == null) {
            res = Math.max(maxDepth, res);
            return;
        }
        maxDepth++;
        setMaxDepth(root.left);
        setMaxDepth(root.right);
        maxDepth--;
    }

    // public static void main(String[] args) {
    //
    //     TreeNode treeNode = new TreeNode(1);
    //     treeNode.left = new TreeNode(2);
    //     treeNode.right = new TreeNode(3);
    //     List<List<Integer>> lists = levelOrder(treeNode);
    //     System.out.println(lists);
    //
    // }

    // 最大深度
    public int maxDepth2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftMax = maxDepth2(root.left);
        int rightMax = maxDepth2(root.right);
        int max = Math.max(leftMax, rightMax);
        return max + 1;
    }

    // 层序遍历
    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> resp = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> levelList = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                levelList.add(poll.val);
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }
            resp.add(levelList);
        }
        return resp;
    }

    // 二叉树转链表 == 先序遍历(左全为空)
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        flatten(root.left);

        flatten(root.right);
        TreeNode temp = root.right;
        root.right = root.left;
        TreeNode p = root;
        while (p.right != null) {
            p = p.right;
        }
        p.right = temp;
        root.left = null;
    }

    public int diam = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        traverse(root);
        return diam;
    }

    // 二叉树直径 1
    public void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        int myDiam = maxDepth3(root.left) + maxDepth(root.right);
        diam = Math.max(diam, myDiam);
        traverse(root.left);
        traverse(root.right);
    }

    public int maxDepth3(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = maxDepth3(root.left);
        int right = maxDepth3(root.right);
        return Math.max(left, right) + 1;
    }

    // 二叉树直径 2  直径:任意节点 两个子树深度之和
    public int diameterOfBinaryTree2(TreeNode root) {
        diameterDepth(root);
        return res;
    }

    public int diameterDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = diameterDepth(root.left);
        int right = diameterDepth(root.right);
        res = Math.max(left + right, res);
        return Math.max(left, right) + 1;
    }

    // 构造:最大二叉树
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        int maxIndex = max(nums);
        int maxNum = nums[maxIndex];
        TreeNode treeNode = new TreeNode(maxNum);
        TreeNode left = null;
        TreeNode right = null;
        if (maxIndex > 0) {
            int[] leftArray = Arrays.copyOfRange(nums, 0, maxIndex - 1);
            left = constructMaximumBinaryTree(leftArray);
        }
        if (maxIndex < nums.length - 1) {
            int[] rightArray = Arrays.copyOfRange(nums, maxIndex + 1, nums.length - 1);
            right = constructMaximumBinaryTree(rightArray);
        }
        treeNode.left = left;
        treeNode.right = right;
        return treeNode;
    }

    public int max(int[] nums) {
        int max = Integer.MIN_VALUE;
        int maxIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) {
                max = nums[i];
                maxIndex = i;
            }
        }
        return maxIndex;
    }

    // 构造:最大二叉树2
    public static TreeNode constructMaximumBinaryTree(int[] nums, int start, int end) {

        int maxIndex = max(nums, start, end);
        int maxNum = nums[maxIndex];
        TreeNode treeNode = new TreeNode(maxNum);
        TreeNode left = null;
        TreeNode right = null;
        if (start == end) {
            return treeNode;
        }
        if (maxIndex > start) {
            left = constructMaximumBinaryTree(nums, start, maxIndex - 1);
        }
        if (maxIndex < end) {
            right = constructMaximumBinaryTree(nums, maxIndex + 1, end);
        }
        treeNode.left = left;
        treeNode.right = right;
        return treeNode;

    }

    public static int max(int[] nums, int start, int end) {
        int max = 0;
        int maxIndex = 0;
        for (int i = start; i <= end; i++) {
            if (nums[i] > max) {
                max = nums[i];
                maxIndex = i;
            }
        }
        return maxIndex;
    }
    // public static void main(String[] args) {
    //     int[] arr = {1,2,3,4,5,6,7};
    //     TreeNode treeNode1 = constructMaximumBinaryTree(arr,0,arr.length-1);
    //     System.out.println(1);
    //
    // }

    /**
     * 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
     * 输出: [3,9,20,null,null,15,7]
     */

    // 根据前序和中序 构建 二叉树
    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0) {
            return null;
        }
        int preIndex = 0;
        int root = preorder[preIndex];
        TreeNode treeNode = new TreeNode(root);
        if (preorder.length == 1) {
            return treeNode;
        }
        int inMiddleIndex = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == root) {
                inMiddleIndex = i;
            }
        }
        int[] leftInorder = Arrays.copyOfRange(inorder, 0, inMiddleIndex);

        int[] rightInorder = Arrays.copyOfRange(inorder, inMiddleIndex + 1, inorder.length);
        int preMiddleIndex = 0;
        outerloop:
        for (int i = 0; i < preorder.length; i++) {
            for (int j = 0; j < rightInorder.length; j++) {
                if (preorder[i] == rightInorder[j]) {
                    preMiddleIndex = i;
                    break outerloop;
                }
            }
        }
        TreeNode left = null;
        TreeNode right = null;
        if (leftInorder.length > 0 && rightInorder.length > 0) {
            int[] leftPreorder = Arrays.copyOfRange(preorder, preIndex + 1, preMiddleIndex);
            left = buildTree(leftPreorder, leftInorder);
            int[] rightPreorder = Arrays.copyOfRange(preorder, preMiddleIndex, inorder.length);
            right = buildTree(rightPreorder, rightInorder);

        } else if (leftInorder.length > 0) {
            // 右边为空
            int[] leftPreorder = Arrays.copyOfRange(preorder, preIndex + 1, preorder.length);
            left = buildTree(leftPreorder, leftInorder);

        } else if (rightInorder.length > 0) {
            // 左边为空
            int[] rightPreorder = Arrays.copyOfRange(preorder, preIndex + 1, inorder.length);
            right = buildTree(rightPreorder, rightInorder);

        }
        treeNode.left = left;
        treeNode.right = right;
        return treeNode;
    }

    // public static void main(String[] args) {
    //     int[] preorder = {3, 9, 20, 15, 7};
    //     int[] inorder = {9, 3, 15, 20, 7};
    //     TreeNode treeNode = buildTree(preorder, inorder);
    //     System.out.println(treeNode);
    // }
    public static HashMap<Integer, Integer> inorderValToIndex = new HashMap<>();

    // 根据前序和中序 构建二叉树 第二种解法
    public static TreeNode buildTree2(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            inorderValToIndex.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);

    }

    public static TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (preStart > preEnd) {
            return null;
        }
        int val = preorder[preStart];
        TreeNode treeNode = new TreeNode(val);
        Integer index = inorderValToIndex.get(val);
        int leftSize = index - inStart;
        TreeNode left = build(preorder, preStart + 1, preStart + leftSize, inorder, inStart, index - 1);
        TreeNode right = build(preorder, preStart + leftSize + 1, preEnd, inorder, index + 1, inEnd);
        treeNode.left = left;
        treeNode.right = right;
        return treeNode;
    }

    // public static void main(String[] args) {
    //     int[] preorder = {3, 9, 20, 15, 7};
    //     int[] inorder = {9, 3, 15, 20, 7};
    //     TreeNode treeNode = buildTree2(preorder, inorder);
    //     System.out.println(treeNode);
    // }

    public static HashMap<Integer, Integer> preOrderValToIndex = new HashMap<>();
    public static HashMap<Integer, Integer> postOrderValToIndex = new HashMap<>();

    //从前序和后续构造二叉树
    public static TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        for (int i = 0; i < preorder.length; i++) {
            preOrderValToIndex.put(preorder[i], i);
        }
        for (int i = 0; i < postorder.length; i++) {
            postOrderValToIndex.put(postorder[i], i);
        }
        return buildFromPrePost(preorder, 0, preorder.length - 1, postorder, 0, postorder.length - 1);


    }

    public static TreeNode buildFromPrePost(int[] preorder, int preStart, int preEnd, int[] postorder, int postStart, int postEnd) {
        if (preStart > preEnd) {
            return null;
        }
        int val = preorder[preStart];
        TreeNode treeNode = new TreeNode(val);
        if (preEnd == preStart) {
            return treeNode;
        }
        // 从后序遍历拿到右侧根节点
        int rightRootVal = postorder[postEnd - 1];
        // 从前序遍历拿到左侧根节点
        int leftRootVal = preorder[preStart + 1];
        Integer preIndex = preOrderValToIndex.get(rightRootVal);
        Integer postIndex = postOrderValToIndex.get(leftRootVal);
        TreeNode left = buildFromPrePost(preorder, preStart + 1, preIndex - 1, postorder, postStart, postIndex);
        TreeNode right = buildFromPrePost(preorder, preIndex, preEnd, postorder, postIndex + 1, postEnd - 1);
        treeNode.left = left;
        treeNode.right = right;
        return treeNode;
    }

    // public static void main(String[] args) {
    //     int[] preorder = {1, 2, 4, 5, 3, 6, 7};
    //     int[] postOrder = {4, 5, 2, 6, 7, 3, 1};
    //     TreeNode treeNode = constructFromPrePost(preorder, postOrder);
    //     System.out.println(treeNode);
    // }

    // 根据前序和中序 构建二叉树 第二种解法
    public static TreeNode buildTree3(int[] inorder, int[]  postOrder) {
        for (int i = 0; i < inorder.length; i++) {
            inorderValToIndex.put(inorder[i], i);
        }
        return buildFromPost(inorder, 0, inorder.length - 1, postOrder, 0, postOrder.length - 1);

    }

    public static TreeNode buildFromPost(int[] inorder, int inStart, int inEnd, int[] postOrder, int postStart, int postEnd) {

        int root = postOrder[postEnd];
        TreeNode treeNode = new TreeNode(root);
        if (inStart == inEnd) {
            return treeNode;
        }
        Integer rootIndex = inorderValToIndex.get(root);
        int leftSize = rootIndex - inStart;
        TreeNode left = buildFromPost(inorder, inStart, rootIndex-1, postOrder, postStart, postStart +leftSize-1);
        TreeNode right = buildFromPost(inorder, rootIndex  + 1, inEnd, postOrder, postStart +leftSize , postEnd-1);
        treeNode.left = left;
        treeNode.right = right;
        return treeNode;
    }

    public static void main(String[] args) {
        int[] inOrder = {2,1};
        int[] postOrder = {1,2};
        TreeNode treeNode = buildTree3(inOrder, postOrder);
        System.out.println(treeNode);
    }
}
